package algorithm.四边形不等式;

public class BestSplitForEveryPosition {

    public static int[] bestSplit1(int[] arr){
        if(arr == null || arr.length == 0){
            return new int[0];
        }

        int[] preSum = new int[arr.length];
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
            preSum[i] = sum;
        }

        int[] result = new int[arr.length];
        int split = 0;
        int max = 0;
        for (int index = 0; index < arr.length; index++) {
            if(index < 1){
                result[index] = 0;
                continue;
            }
            while(split < index){
                int left = preSum[split];
                int right = preSum[index] - preSum[split];
                int tmp = Math.min(left, right);
                if(tmp >= max){
                    max = tmp;
                    result[index] = tmp;
                }
                if(Math.min(preSum[split + 1], preSum[index] - preSum[split + 1]) >= max){
                    split++;
                }else
                    break;
            }
        }
        return result;

    }


    public static int[] bestSplit2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return new int[0];
        }
        int N = arr.length;
        int[] ans = new int[N];
        ans[0] = 0;
        for (int range = 1; range < N; range++) {
            for (int s = 0; s < range; s++) {
                int sumL = 0;
                for (int L = 0; L <= s; L++) {
                    sumL += arr[L];
                }
                int sumR = 0;
                for (int R = s + 1; R <= range; R++) {
                    sumR += arr[R];
                }
                ans[range] = Math.max(ans[range], Math.min(sumL, sumR));
            }
        }
        return ans;
    }

    public static int[] randomArray(int len, int max) {
        int[] ans = new int[len];
        for (int i = 0; i < len; i++) {
            ans[i] = (int) (Math.random() * max);
        }
        return ans;
    }

    public static boolean isSameArray(int[] arr1, int[] arr2) {
        if (arr1.length != arr2.length) {
            return false;
        }
        int N = arr1.length;
        for (int i = 0; i < N; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int N = 20;
        int max = 30;
        int testTime = 1000000;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            int len = (int) (Math.random() * N);
            int[] arr = randomArray(len, max);
            int[] ans1 = bestSplit1(arr);
            int[] ans2 = bestSplit2(arr);
            if (!isSameArray(ans1, ans2)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("测试结束");
    }
}
